home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group00a.txt
/
000113_icon-group-sender _Fri May 19 12:25:07 2000.msg
< prev
next >
Wrap
Internet Message Format
|
2001-01-03
|
5KB
Return-Path: <icon-group-sender>
Received: (from root@localhost)
by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id MAA02361
for icon-group-addresses; Fri, 19 May 2000 12:24:33 -0700 (MST)
Message-Id: <200005191924.MAA02361@baskerville.CS.Arizona.EDU>
From: espie@liafa.jussieu.fr (Marc Espie)
X-Newsgroups: comp.lang.icon
Subject: Re: Is Anyone Working On A Unicode Version Of Icon?
Date: 19 May 2000 15:09:30 GMT
X-Trace: vishnu.jussieu.fr 958748970 2780 132.227.81.128 (19 May 2000 15:09:30 GMT)
X-Complaints-To: Newsmaster@jussieu.fr.
X-Newsreader: trn 4.0-test70 (17 January 1999)
To: icon-group@optima.CS.Arizona.EDU
Errors-To: icon-group-errors@optima.CS.Arizona.EDU
Status: RO
In article <200005172324.QAA19139@baskerville.CS.Arizona.EDU>,
Ian Trudel <ian.trudel@tr.cgocable.ca> wrote:
>> >5/ and finaly, speed issue only speaks by benchmarking.
>> I've run some fairly large icon projects in the past. I have a fairly good
>> idea about what slowed them down eventually. I even have a submitted paper
>> to a conference that pits icon against maple and C++.
>
>Now that's interesting, is your paper online?
Not yet, sorry. There are proceedings involved, and I'll have to see if
there is red tape involved with Springer.
Briefly put, the gist of the matter was to compare methods to generate
Dyck words (well-parenthesized words).
I asked a friend who is a typical user of maple to write it in a way natural
to maple, which I compared to the typical icon generator:
procedure dyck(n)
if n = 0 then
suspend ""
else
every i := 0 to n-1 do
suspend "("||dyck(i)||")"||dyck(n-i-1)
end
As far as C++ goes, I exposed a simple technique to `revert' generators
control, e.g, model
every write(gen())
as an `application of' every(write(.)) to gen.
The traditional icon implementation does have write call gen repetitively.
Instead, we have gen produce results and pass them to a `continuation' of
write that tells whether it needs more results. This combines nicely with
the Template Method design pattern, and leads to an almost automatic
translation to C++ that does not need any extra control structures to handle
generators (e.g., the program flow is more or less hardcoded into templates).
For Dyck words, the results looks like (more or less, generator.h left
aside for brevity):
#include <string>
#include "generator.h"
class DyckWord3: public Function<string> {
const Function<string>& f; const string& b;
public:
DyckWord3(const string& b_, const Function<string>& f_):
f(f_), b(b_) {}
bool operator() (const string& e) const {
return f(b+e);
}
};
class DyckWord2: public Generator<string> { const string& a; int r;
public:
DyckWord2(const string& a_, int r_): a(a_), r(r_) {}
bool iterate(const Function<string>& consume) const;
};
class DyckWord1: public Function<string> {
const Function<string>& f; const int n;
public:
DyckWord1(const Function<string>& f_, int n_): f(f_), n(n_) {}
bool operator()(const string &a) const {
return DyckWord2("("+a+")", n).iterate(f);
}
};
class DyckWord: public Generator<string> { const int n;
public:
DyckWord(int n_): n(n_) {}
bool iterate(const Function<string>& consume) const {
if (n == 0) return consume("");
else for (int i = 0; i < n; i++)
if (!DyckWord(i).iterate(DyckWord1(consume, n-1-i)))
return false;
return true;
}
};
bool DyckWord2::iterate(const Function<string>& consume) const {
return DyckWord(r).iterate(DyckWord3(a, consume));
}
Granted, this is somewhat longer than the icon version.
Both the Icon and C++ version outperform Maple by a huge factor (as maple
is not geared toward generators, and the traditional Dyck word generator
is memory-heavy). Somewhat surprisingly, the C++ implementation is not much
faster than the Icon implementation (factor of 3). This was traced down
to the particular C++ string implementation not being well-suited to the job
at hand.
In similar cases where strings are not involved and where memory consumption
can be taken out of the way (permutations, with in-place list construction),
C++ outperforms icon by a factor of 10 or more, which is quite logical.
The Icon compiler does not gain that much, which was to be expected as well.
--
Marc Espie
|anime, sf, juggling, unicycle, acrobatics, comics...
|AmigaOS, OpenBSD, C++, perl, Icon, PostScript...
| `real programmers don't die, they just get out of beta'